/*
 * Grafo.cpp
 *
 *  Created on: 30/ott/2013
 *      Author: angelo
 */

#include "Grafo.h"

Grafo::Grafo() {
	nodo = NULL;
	figli.clear();

	nextGraph = this;
	previousGraph = this;

	nStemNodes = 0;
	for (int i = 0; i < MAX_PARALLEL_THREADS; i++) {
		activeMVC[i] = false;
	}
	stemCost = -1;
	distanceCost = 0.0;
	stemWidth = 0;
	distanceStemStepCost = 0.0;
}

Grafo::Grafo(Node *n) {
	nodo = n;
	figli.clear();

	nextGraph = this;
	previousGraph = this;

	nStemNodes = 1;
	for (int i = 0; i < MAX_PARALLEL_THREADS; i++) {
		activeMVC[i] = true;
	}
	stemCost = -1;
	distanceCost = 0.0;
	stemWidth = 0;
	distanceStemStepCost = 0.0;
}

Grafo::~Grafo() {}

int Grafo::getStemCost(void) const {
	return stemCost;
}

void Grafo::setStemCost(int stemCost) {
	this->stemCost = stemCost;
}
int Grafo::getDistanceCost(void) const {
	return distanceCost;
}

void Grafo::setDistanceCost(int distanceCost) {
	this->distanceCost = distanceCost;
}

double Grafo::getDistanceStemStepCost() const {
	return distanceStemStepCost;
}

void Grafo::setDistanceStemStepCost(double distanceStemStepCost) {
	this->distanceStemStepCost = distanceStemStepCost;
}

int Grafo::getStemWidth(void) const {
	return stemWidth;
}

void Grafo::setStemWidth(int stemWidth) {
	this->stemWidth = stemWidth;
}

void Grafo::reactivateAllNodes(int thr_idx) {
	Grafo *g;
	list<Grafo *>::iterator it;

	// conto i vertici usando la lista circolare che collega tutti i vertici
	if (nodo != NULL) {

		g = nextGraph;

		while (g != this) {
			g->activeMVC[thr_idx] = true;

			for (it = g->figli.begin(); it != g->figli.end(); it++) {
				(*it)->activeMVC[thr_idx] = true;
			}

			g = g->nextGraph;
		}
	}
}

void Grafo::createFromStemIslands(StemIslands *si) {
	list<StemIsland *>::iterator it_si;
	Grafo *newG, *oldG, *actualG, *pointedG;

	//if(nStemNodes == 0) return;

	newG = oldG = this;

	for (it_si = si->stem_nodes.begin(); it_si != si->stem_nodes.end(); it_si++) {
		if(nodo == NULL) {
			nodo = *it_si;
			nStemNodes = 1;
		}
		else {
			newG = new Grafo(*it_si);

			// faccio i collegamenti incrociati
			oldG->nextGraph = newG;
			newG->previousGraph = oldG;

			//faccio un passo con oldG
			oldG = newG;

			// mi segno che ho aggiunto un nuovo STEM
			nStemNodes++;
		}
	}
	// faccio l'ultimo collegamento per chiudere il cerchio
	newG->nextGraph = this;
	this->previousGraph = newG;

	// creo le connessioni del grafo (creo un grafo connesso)
	actualG = this;
	do {
		pointedG = actualG->nextGraph;

		while(pointedG != actualG) {
			actualG->figli.push_front(pointedG);

			// vado avanti
			pointedG = pointedG->nextGraph;
		}

		// visto che ci sono, aggiorno tutti i grafi con il valore corretto del numero di STEM nodes presenti nel grafo
		actualG->nStemNodes = nStemNodes;

		//vado al prossimo
		actualG = actualG->nextGraph;

	} while(actualG != this);
}

void Grafo::add3SteinerPoints(void) {
	//Grafo *g1, *g2, *g3;
	Grafo *g[3];
	int i;

	if(nStemNodes < 3) return;

	g[0] = this;
	g[1] = g[0]->nextGraph;
	g[2] = g[1]->nextGraph;

	// faccio un controllo che potrei non fare, non dovrebbe mai essere
	if((g[0] == g[1]) || (g[0] == g[2]) || (g[2] == g[1])) return;

	while (g[2] != this) {	// controllo che g[2] non abbia fatto tutto il giro
		while (g[2] != this) {	// controllo che g[2] non abbia fatto tutto il giro
			while (g[2] != this) {	// controllo che g[2] non abbia fatto tutto il giro
				// controllo steiner ed eventualmente lo aggiungo
				// controllo che tutti e tre gli angoli siano < PI*2/3
				bool calculateSteiner = true;

				// Lo Steiner-point esiste (diverso dai tre punti di input) solo se gli angoli sono tutti minori di 120°
				for(i = 0; i < 3; i++) {
					if (Coordinates::calculateAngle(
							g[i]->nodo->pos, g[((i+1)%3)]->nodo->pos, g[((i+2)%3)]->nodo->pos) >= ((M_PI * 2) / 3)) {
						calculateSteiner = false;
						break;
					}
				}

				if (calculateSteiner) {
					Coordinates sPoint = Coordinates::calculateSteinerPoint(g[0]->nodo->pos, g[1]->nodo->pos, g[2]->nodo->pos);

					if (sPoint != Coordinates::ZERO) {
						//creo il nuovo nodo Steiner
						SteinerNode *newSt = new SteinerNode();
						newSt->pos = sPoint;
						newSt->addStems((StemIsland *) g[0]->nodo, (StemIsland *) g[1]->nodo, (StemIsland *) g[2]->nodo);

						Grafo *newSteinerG = new Grafo(newSt);
						// aggiungo i suoi unici tre figli che sono i nodi su cui è stato calcolato
						newSteinerG->figli.push_back(g[0]);
						newSteinerG->figli.push_back(g[1]);
						newSteinerG->figli.push_back(g[2]);

						// lo aggancio agli stem node
						for(i = 0; i < 3; i++) {
							g[i]->figli.push_back(newSteinerG);
						}
					}
					else {
						cout << "Error calculating the Steiner point for: "
								<< g[0]->nodo->pos << " " << g[1]->nodo->pos << " " << g[2]->nodo->pos << endl;
					}
				}

				//faccio un passo avanti con g[2];
				g[2] = g[2]->nextGraph;
			}

			//faccio un passo avanti con g[1];
			g[1] = g[1]->nextGraph;
			g[2] = g[1]->nextGraph;
		}

		//faccio un passo avanti con g[0];
		g[0] = g[0]->nextGraph;
		g[1] = g[0]->nextGraph;
		g[2] = g[1]->nextGraph;
	}
}

int Grafo::cost(void) {
	int ris = 0;
	Grafo *g;

	// conto i vertici usando la lista circolare che collega tutti i vertici
	if (nodo != NULL) {

		g = nextGraph;
		ris++;

		while (g != this) {
			ris++;
			g = g->nextGraph;
		}
	}

	return ris;
}

Grafo *Grafo::MVCseekerParallel(double radius, int budget, int nthreadsActive) {
	Grafo *ris = NULL;
	Grafo *g = this;
	int nStem = nStemNodes;
	int i = 0;
	int tid, nthreads, counter, actStem;

	Grafo *gArray[nStemNodes];
	Grafo *local[nStemNodes];
	Grafo *localGlobal[nStemNodes];

	counter = 0;
	actStem = 0;

	// inizializzo il vettore dei nodi del grafo
	// inserisco i nodi su cui devo iterare in un array
	if (nodo != NULL) {
		do {
			gArray[i] = g;
			local[i] = new Grafo();
			localGlobal[i] = NULL;

			i++;

			g = g->nextGraph;
		} while (g != this);
	}

	// ciclo su ogni nodo del grafo
	if (nodo != NULL) {
		#pragma omp parallel private(tid, nthreads) shared(gArray, local, localGlobal, nStem, counter, actStem)
		{
			/* get the current thread ID in the parallel region */
			tid = omp_get_thread_num();

			/* get the total number of threads available in this parallel region */
			nthreads = omp_get_num_threads();

			if (tid >= nthreadsActive) {
				#pragma omp critical
				{
					cout << "Thread ID " << tid << " not necessary. Number of thread enabled: " << nthreadsActive << endl;
				}
			}
			else {

				do {
					int myact;
					list<Grafo *> boundary;

					#pragma omp critical
					{
						myact = actStem;
						actStem++;
					}

					if (myact >= nStem) {
						break;
					}

					boundary.clear();
					boundary.push_back(gArray[myact]);	// inizializzo il boundary con il nodo corrente

					reactivateAllNodes(tid);

					#pragma omp critical
					{
						cout << "Thread ID " << tid << "; Progress " << myact << " for " << nStem << " stem nodes: " << ((double)myact / (double)nStem) * 100.0 << "%" << endl;
						//cout << "Progress " << counter << " for " << nStem << " stem nodes: " << ((double)counter / (double)nStem) * 100.0 << "%" << endl;
						//counter++;
					}

					findBestTree(boundary, budget, radius, NULL, local[myact], localGlobal[myact], 0, 0.0, 0, 0.0, tid);

					#pragma omp critical
					{
						//cout << "Progress " << counter << " for " << nStem << " stem nodes: " << ((double)counter / (double)nStem) * 100.0 << "%" << endl;
						counter++;
						cout << "Thread ID " << tid << " finished starting from " << myact << " -> " << ((double)counter / (double)nStem) * 100.0 << "%" << endl;
					}

				} while (true);

				/*
				for (int j = tid; j < nStem; j += nthreads) {
					list<Grafo *> boundary;

					boundary.clear();
					boundary.push_back(gArray[j]);	// inizializzo il boundary con il nodo corrente

					reactivateAllNodes(tid);

					#pragma omp critical
					{
						cout << "Progress " << counter << " for " << nStem << " stem nodes: " << ((double)counter / (double)nStem) * 100.0 << "%" << endl;
						counter++;
					}

					findBestTree(boundary, budget, radius, NULL, local[j], localGlobal[j], 0, 0.0, 0, 0.0, tid);
				}
				*/
			}
		}
	}
	cout << "Progress " << nStem << " for " << nStem << " stem nodes: 100%" << endl;

	// dopo che tutti hanno calcolato il loro grafo migliore, controllo quale è il migliore tra tutti
	for (i = 0; i < nStemNodes; i++) {
		if (localGlobal[i] != NULL) {
			if (	(ris == NULL) || (ris->nodo == NULL)

					||

					(localGlobal[i]->getStemWidth() > ris->getStemWidth())

					||

					(	(localGlobal[i]->getStemWidth() == ris->getStemWidth()) &&
						(localGlobal[i]->getStemCost() < ris->getStemCost()))

					||

					(	(localGlobal[i]->getStemWidth() == ris->getStemWidth()) &&
						(localGlobal[i]->getStemCost() == ris->getStemCost()) &&
						(localGlobal[i]->getDistanceCost() < ris->getDistanceCost()))

					||

					(	(localGlobal[i]->getStemWidth() == ris->getStemWidth()) &&
						(localGlobal[i]->getStemCost() == ris->getStemCost()) &&
						(localGlobal[i]->getDistanceCost() == ris->getDistanceCost()) &&
						(localGlobal[i]->getDistanceStemStepCost() < ris->getDistanceStemStepCost()))
			){
				ris = localGlobal[i];
			}
		}
	}

	if (ris == NULL) {
		// non sono riuscito a fare niente, creo un grafo vuoto
		ris = new Grafo();
	}

	return ris;
}

Grafo *Grafo::MVCseeker(double radius, int budget) {
	Grafo *ris = NULL;
	Grafo *g = this;
	int counter, nStem;
	int my_thr_idx = 0;

	nStem = nStemNodes;
	counter = 0;

	// ciclo su ogni nodo del grafo
	if (nodo != NULL) {
		do {
			Grafo *local = new Grafo();
			list<Grafo *> boundary;


			boundary.clear();
			boundary.push_back(g);	// inizializzo il boundary con il nodo corrente

			reactivateAllNodes(my_thr_idx);

			cout << "Progress " << counter << " for " << nStem << " stem nodes: " << ((double)counter / (double)nStem) * 100.0 << "%" << endl;

			findBestTree(boundary, budget, radius, NULL, local, ris, 0, 0.0, 0, 0.0, my_thr_idx);

			g = g->nextGraph;
			counter++;
		} while (g != this);

		cout << "Progress " << nStem << " for " << nStem << " stem nodes: 100%" << endl;
	}

	if (ris == NULL) {
		// non sono riuscito a fare niente, creo un grafo vuoto
		ris = new Grafo();
	}

	return ris;
}

int Grafo::calculateWidth(Grafo *prevNode, Grafo *actualNode) {
	int ris = 0;
	list<Grafo *>::iterator it;

	if (actualNode->nodo->isSteinerNode()) {
		// il nodo steiner ha sempre tre figli
		for(it = actualNode->figli.begin(); it != actualNode->figli.end(); it++) {
			if ((*it)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
				continue;
			}

			// sommo la cardinalità dei due nodi
			ris += (*it)->nodo->getNodeCardinality();
		}
	}
	else {
		ris = actualNode->nodo->getNodeCardinality();
	}

	return ris;
}

double Grafo::calculateDistanceCost(Grafo *prevNode, Grafo *actualNode) {
	double ris = 0.0;

	if (prevNode == NULL) {
		ris = 0;
	}
	else if (!(actualNode->nodo->isSteinerNode())) {
		ris = prevNode->nodo->pos.distance(actualNode->nodo->pos);
	}
	else {
		list<Grafo *>::iterator it;

		// il nodo steiner ha sempre tre figli
		for(it = actualNode->figli.begin(); it != actualNode->figli.end(); it++) {
			ris += actualNode->nodo->pos.distance((*it)->nodo->pos);
		}
	}

	return ris;
}

int Grafo::calculateCost(Grafo *prevNode, Grafo *actualNode, double radius, double &distanceStemsCost) {
	int ris = 0;

	if (prevNode == NULL) {
		ris = 1;
		distanceStemsCost = 0.0;
	}
	else if (!(actualNode->nodo->isSteinerNode())) {
		ris = ceil(prevNode->nodo->pos.distance(actualNode->nodo->pos) / radius);
		if(ris == 0) {
			ris = 1;	// se i due nodi sono sovrapposti, comunque ci vuole un nodo
		}

		distanceStemsCost = prevNode->nodo->pos.distance(actualNode->nodo->pos);
	}
	else {
		Node *nodes[3];
		int i = 0;
		list<Grafo *>::iterator it;
		int u1, u2, u3, idx2, idx3;
		double r1, r2, g12, g13, g23;

		distanceStemsCost = 0.0;

		// il nodo steiner ha sempre tre figli
		nodes[i++] = prevNode->nodo;
		for(it = actualNode->figli.begin(); it != actualNode->figli.end(); it++) {
			if((i < 3) && ((*it)->nodo->getNodeID() != prevNode->nodo->getNodeID())) {
				nodes[i++] = (*it)->nodo;
			}
		}

		// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
		u1 = ceil(nodes[0]->pos.distance(actualNode->nodo->pos) / radius) - 1;	 // non metto il nodo sullo steiner
		if (u1 < 0){
			u1 = 0;
		}
		/*if (nodes[0]->pos.distance(actualNode->nodo->pos) == radius) {
			u1 = 0;
		}*/

		distanceStemsCost += u1 * radius;
		Coordinates pointerVector1 = (actualNode->nodo->pos - nodes[0]->pos) / actualNode->nodo->pos.distance(nodes[0]->pos);
		Coordinates lastPoint1 = nodes[0]->pos + (pointerVector1 * (u1 * radius));

		// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
		r1 = nodes[0]->pos.distance(actualNode->nodo->pos) - (((double) u1) * radius);

		// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
		// sui segmenti rimanenti steiner<->2, steiner<->3
		g12 = g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r1 / radius) * (M_SQRT3 / 2.0)) );

		// cerco il segmento tra 2 e 3 più lungo dallo stainer
		if (	(nodes[1]->pos.distance(actualNode->nodo->pos)) >
				(nodes[2]->pos.distance(actualNode->nodo->pos)) ) {
			idx2 = 1;
			idx3 = 2;
		}
		else {
			idx2 = 2;
			idx3 = 1;
		}

		Coordinates pointerVector2 = (nodes[idx2]->pos - actualNode->nodo->pos) / actualNode->nodo->pos.distance(nodes[idx2]->pos);
		Coordinates pointerVector3 = (nodes[idx3]->pos - actualNode->nodo->pos) / actualNode->nodo->pos.distance(nodes[idx3]->pos);
		Coordinates firstPoint2, firstPoint3;

		if (g12 >= nodes[idx2]->pos.distance(actualNode->nodo->pos)) {
			// controllo se il nodo si trova nel raggio di copertura del precedente
			u2 = 1;	// mi serve solo 1 per coprire il nodo

			r2 = nodes[idx2]->pos.distance(actualNode->nodo->pos);

			firstPoint2 = nodes[idx2]->pos;
			distanceStemsCost += firstPoint2.distance(lastPoint1);	// aggiungo la distanza diretta
		}
		else {
			u2 = ceil((nodes[idx2]->pos.distance(actualNode->nodo->pos) - g12) / radius) + 1;

			r2 = g12;

			firstPoint2 = actualNode->nodo->pos + (pointerVector2 * g12);
			distanceStemsCost += firstPoint2.distance(lastPoint1);
			distanceStemsCost += firstPoint2.distance(nodes[idx2]->pos);
		}

		g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r2 / radius) * (M_SQRT3 / 2.0)) );


		if (max(g13, g23) >= nodes[idx3]->pos.distance(actualNode->nodo->pos)) {
			u3 = 1;

			firstPoint3 = nodes[idx3]->pos;
			if (g13 >= g23) {
				distanceStemsCost += firstPoint3.distance(lastPoint1);		// aggiungo la distanza diretta
			}
			else {
				distanceStemsCost += firstPoint3.distance(firstPoint2);	// aggiungo la distanza diretta
			}
		}
		else {
			u3 = ceil((nodes[idx3]->pos.distance(actualNode->nodo->pos) - max(g13, g23)) / radius) + 1;

			firstPoint3 = actualNode->nodo->pos + (pointerVector3 * max(g13, g23));
			if (g13 >= g23) {
				distanceStemsCost += firstPoint3.distance(lastPoint1);
			}
			else {
				distanceStemsCost += firstPoint3.distance(firstPoint2);
			}
			distanceStemsCost += firstPoint3.distance(nodes[idx3]->pos);
		}

		ris = u1 + u2 + u3;
	}

	return ris;
}

int Grafo::calculateCostOld(Grafo *prevNode, Grafo *actualNode, double radius) {
	int ris = 0;

	if (prevNode == NULL) {
		ris = 1;
	}
	else if (!(actualNode->nodo->isSteinerNode())) {
		ris = ceil(prevNode->nodo->pos.distance(actualNode->nodo->pos) / radius);
		if(ris == 0) {
			ris = 1;	// se i due nodi sono sovrapposti, comunque ci vuole un nodo
		}
	}
	else {
		Node *nodes[3];
		int i = 0;
		list<Grafo *>::iterator it;
		int tot_cost[3];

		// il nodo steiner ha sempre tre figli
		for(it = actualNode->figli.begin(); it != actualNode->figli.end(); it++) {
			if(i < 3) {
				nodes[i++] = (*it)->nodo;
			}
		}

		for (i = 0; i < 3; i++) {
			// provo a calcolare il costo a partire da ogniuno dei tre vertici e alla fine prendo il meno costoso
			// (costeranno tutti uguale??? mah!)
			int u1, u2, u3, idx2, idx3;
			double r1, r2, g12, g13, g23;

			// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
			u1 = floor(nodes[((i + 0) % 3)]->pos.distance(actualNode->nodo->pos) / radius);	 // non metto il nodo sullo steiner
			if (nodes[((i + 0) % 3)]->pos.distance(actualNode->nodo->pos) == radius) {
				u1 = 0;
			}

			// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
			r1 = nodes[((i + 0) % 3)]->pos.distance(actualNode->nodo->pos) - (((double) u1) * radius);

			// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
			// sui segmenti rimanenti steiner<->2, steiner<->3
			g12 = g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r1 / radius) * (M_SQRT3 / 2.0)) );

			// cerco il segmento tra 2 e 3 più lungo dallo stainer
			if (	(nodes[((i + 1) % 3)]->pos.distance(actualNode->nodo->pos)) >
					(nodes[((i + 2) % 3)]->pos.distance(actualNode->nodo->pos)) ) {
				idx2 = (i + 1) % 3;
				idx3 = (i + 2) % 3;
			}
			else {
				idx2 = (i + 2) % 3;
				idx3 = (i + 1) % 3;
			}

			if (g12 >= nodes[idx2]->pos.distance(actualNode->nodo->pos)) {
				// controllo se il nodo si trova nel raggio di copertura del precedente
				u2 = 1;	// mi serve solo 1 per coprire il nodo

				r2 = nodes[idx2]->pos.distance(actualNode->nodo->pos);
			}
			else {
				u2 = ceil((nodes[idx2]->pos.distance(actualNode->nodo->pos) - g12) / radius) + 1;

				r2 = g12;
			}

			g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r2 / radius) * (M_SQRT3 / 2.0)) );


			if (max(g13, g23) >= nodes[idx3]->pos.distance(actualNode->nodo->pos)) {
				u3 = 1;
			}
			else {
				u3 = ceil((nodes[idx3]->pos.distance(actualNode->nodo->pos) - max(g13, g23)) / radius) + 1;
			}

			tot_cost[i] = u1 + u2 + u3;
		}

		ris = min(tot_cost[0],  min(tot_cost[1], tot_cost[2]));
	}

	return ris;
}

bool Grafo::checkActive(Grafo *prevNode, Grafo *actualNode, int thr_idx) {
	list<Grafo *>::iterator it;
	bool ris = false;

	//cout << "Grafo::checkActive: " << "BEGIN" << endl;

	if (!(actualNode->nodo->isSteinerNode())) {
		ris = actualNode->activeMVC[thr_idx];
	}
	else {
		ris = true;

		// il nodo steiner ha sempre tre figli
		for(it = actualNode->figli.begin(); it != actualNode->figli.end(); it++) {
			if ((*it)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
				continue;
			}

			// devono essere entrambi attivi
			ris = ris && (*it)->activeMVC[thr_idx];
		}
	}

	//cout << "Grafo::checkActive: " << "END" << endl;

	return ris;
}

bool Grafo::checkLink(Grafo *prevNode, Grafo *actualNode) {
	list<Grafo *>::iterator it;
	bool ris = false;

	//cout << "Grafo::findBestTree: " << "BEGIN" << endl;

	if (prevNode == NULL) {
		ris = true;
	}
	else {
		for(it = prevNode->figli.begin(); it != prevNode->figli.end(); it++) {
			if ((*it)->nodo->getNodeID() == actualNode->nodo->getNodeID()) {
				ris = true;
				break;
			}
		}
	}

	//cout << "Grafo::findBestTree: " << "END" << endl;

	return ris;
}

void Grafo::addNode(Grafo *parentNode, Grafo *actualNode) {
	// devo cercare il nodo parent e quindi poi aggiungere actualNode come suo figlio
	//if ((parentNode == NULL) || (nodo == NULL)) return; //caso particolare che non dovrebbe mai accadere
	//cout << "Grafo::addNode: " << "Start" << endl;
	//if (parentNode == NULL) return; //caso particolare che non dovrebbe mai accadere

	//cout << "Grafo::addNode: " << "0, parent: " << parentNode << endl;

	if ((parentNode == NULL) || (parentNode->nodo == NULL)) {
		// albero vuoto, aggiungo il singolo nodo
		//cout << "Grafo::addNode: " << "1" << endl;
		figli.clear();
		nodo = actualNode->nodo;
	}
	else {
		//cout << "Grafo::addNode: " << "1.2 " << nodo << endl;
		// faccio un controllo ricorsivo
		if (nodo->getNodeID() == parentNode->nodo->getNodeID()) {

			//cout << "Grafo::addNode: " << "2" << endl;

			//trovato il parent, aggiungo actual ai suoi figli
			Grafo *newGraphNode = new Grafo(actualNode->nodo);
			figli.push_back(newGraphNode);

			//cout << "Grafo::addNode: " << "3" << endl;

			//dopo averlo aggiunto nel grafo, lo inserisco anche nella lista circolare
			// lo inserisco dopo di me
			newGraphNode->nextGraph = nextGraph;
			nextGraph = newGraphNode;
			newGraphNode->previousGraph = this;
			if (previousGraph == this) previousGraph = newGraphNode;
		}
		else {
			// lo faccio ricorsivamente su tutti i miei nodi figli
			//cout << "Grafo::addNode: " << "4" << endl;
			for (list<Grafo *>::iterator it = figli.begin(); it != figli.end(); it++) {
				(*it)->addNode(parentNode, actualNode);
			}
		}
	}

	//cout << "Grafo::addNode: " << "End" << endl;
}

void Grafo::removeNode(Grafo *parentNode, Grafo *actualNode) {
	// devo cercare il nodo parent e quindi poi rimuovere actualNode come suo figlio
	//if(parentNode == NULL) return; //caso particolare che non dovrebbe mai accadere

	//cout << "Grafo::removeNode: " << "Start" << endl;

	if ((parentNode == NULL) || (parentNode->nodo == NULL)) {
		// albero vuoto, rimuovo me stesso
		//cout << "Grafo::removeNode: " << "1" << endl;
		figli.clear();
		nodo = NULL;
	}
	else {
		//cout << "Grafo::removeNode: " << "2, nodo: " << nodo << endl;
		// faccio un controllo ricorsivo
		if (nodo->getNodeID() == parentNode->nodo->getNodeID()) {
			//trovato il parent, rimuovo actual dai suoi figli
			//cout << "Grafo::removeNode: " << "3" << endl;
			for (list<Grafo *>::iterator it = figli.begin(); it != figli.end(); it++) {
				if ((*it)->nodo->getNodeID() == actualNode->nodo->getNodeID()) {

					Grafo *g_remove = *it;

					// prima di toglierlo dal grafo lo rimuovo anche dalla lista circolare
					Grafo *g = this;
					do {
						if (g->nodo->getNodeID() == g_remove->nodo->getNodeID()) {
							//trovato
							g_remove->previousGraph->nextGraph = g_remove->nextGraph;
							g_remove->nextGraph->previousGraph = g_remove->previousGraph;

							break;
						}

						g = g->nextGraph;
					} while (g != this);

					figli.erase(it);
					free (g_remove);

					break;
				}
			}
		}
		else {
			// lo faccio ricorsivamente su tutti i miei nodi figli
			//cout << "Grafo::removeNode: " << "4" << endl;
			for (list<Grafo *>::iterator it = figli.begin(); it != figli.end(); it++) {
				(*it)->removeNode(parentNode, actualNode);
			}
		}
	}

	//cout << "Grafo::removeNode: " << "End" << endl;
}

void Grafo::findBestTree(list<Grafo *> &boundary, int budget, double radius, Grafo *prevNode,
		Grafo * &local, Grafo * &global, int actualTreeCost, double actualTreeDistanceCost,
		int actualTreeWidth, double actualTreeDistanceStemStepCost, int thr_idx) {
	list<Grafo *>::iterator it_border, it_b2;
	bool checkTree = true;

	for (it_border = boundary.begin(); it_border != boundary.end(); it_border++) {
		double distanceStemStepCost = 0;
		int cost_step = calculateCost(prevNode, *it_border, radius, distanceStemStepCost);
		int widthGain_step = calculateWidth(prevNode, *it_border);
		double dist_cost_step = calculateDistanceCost(prevNode, *it_border);
		bool boundaryNodeActive = checkActive(prevNode, *it_border, thr_idx);
		bool linkPresent = checkLink(prevNode, *it_border);

		//cout << "Grafo::findBestTree: " << 1 << endl;

		// controllo sia che il costo del collegamento è fattibile,
		// sia se il nodo della boundary è attivo (dovrebbe) e, in particolare, se è steiner
		// controllo se entrambi i nodi collegati allo stainer siano entrambi attivi
		if ((cost_step <= budget) && (boundaryNodeActive) && (linkPresent)) {
			list<Grafo *>::iterator it_figli, it_figli2, it_new_b;
			list<Grafo *> newBoundary;

			// posso fare ancore un altro passo, non faccio il controllo dell'albero
			checkTree = false;

			for (it_b2 = boundary.begin(); it_b2 != boundary.end(); it_b2++) {
				// creo la nuova border line. Parto con quella precedente senza il nodo attuale inserendo solo i nodi attivi
				if ((it_b2 != it_border) && ((*it_b2)->activeMVC[thr_idx])) {
					// il nodo che aggiungo nella nuova boundary deve essere attivo, altrimenti vuol dire che l'ho già inserito nellalbero
					newBoundary.push_back(*it_b2);
				}
			}

			if ((*it_border)->nodo->isSteinerNode()) {
				// se sono uno steiner nodo cerco di prendere tre nodi insieme
				// i figli dello steiner sono sepre tre, di cui uno è il "prevNode"
				for (it_figli = (*it_border)->figli.begin(); it_figli != (*it_border)->figli.end(); it_figli++) {
					if ((*it_figli)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
						continue;
					}

					// aggiungo i figli di entrambi i nodi collegati allo stainer
					for (it_figli2 = (*it_figli)->figli.begin(); it_figli2 != (*it_figli)->figli.end(); it_figli2++) {
						if ((*it_figli2)->activeMVC[thr_idx]){
							// mi assicuro che il nodo non sia già presente nell'albero che sto costruendo
							bool already_present = false;

							for (it_new_b = newBoundary.begin(); it_new_b != newBoundary.end(); it_new_b++) {
								if((*it_new_b)->nodo->getNodeID() == (*it_figli2)->nodo->getNodeID()) {
									already_present = true;
									break;
								}
							}

							if(!already_present) {		// non è già presente, lo aggiungo
								newBoundary.push_back(*it_figli2);
							}
						}
					}
				}

				// elimino il nodo dalla border e lo disattivo per evitare cicli e li aggiungo all'albero
				(*it_border)->activeMVC[thr_idx] = false;
				local->addNode(prevNode, *it_border);
				for (it_figli = (*it_border)->figli.begin(); it_figli != (*it_border)->figli.end(); it_figli++) {
					if ((*it_figli)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
						continue;
					}

					(*it_figli)->activeMVC[thr_idx] = false;
					local->addNode(*it_border, *it_figli);
				}

				// CHIAMATA RICORSIVA!
				//faccio due chiamate ricorsive, che partono dai due nodi collegati allo stainer
				for (it_figli = (*it_border)->figli.begin(); it_figli != (*it_border)->figli.end(); it_figli++) {
					if ((*it_figli)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
						continue;
					}

					findBestTree(newBoundary, budget - cost_step, radius, *it_figli, local, global,
							actualTreeCost + cost_step, actualTreeDistanceCost + dist_cost_step,
							actualTreeWidth + widthGain_step, actualTreeDistanceStemStepCost + distanceStemStepCost,
							thr_idx);
				}

				// riattivo i nodi
				for (it_figli = (*it_border)->figli.begin(); it_figli != (*it_border)->figli.end(); it_figli++) {
					if ((*it_figli)->nodo->getNodeID() == prevNode->nodo->getNodeID()) {
						continue;
					}

					(*it_figli)->activeMVC[thr_idx] = true;
					local->removeNode(*it_border, *it_figli);
				}
				(*it_border)->activeMVC[thr_idx] = true;
				local->removeNode(prevNode, *it_border);
			}
			else {

				// aggiungo tutti i vicini del nodo corrente (attivi) che non siano già presenti nella borderline
				for (it_figli = (*it_border)->figli.begin(); it_figli != (*it_border)->figli.end(); it_figli++) {
					if ((*it_figli)->activeMVC[thr_idx]){
						// mi assicuro che il nodo non sia già presente nell'albero che sto costruendo
						bool already_present = false;

						for (it_new_b = newBoundary.begin(); it_new_b != newBoundary.end(); it_new_b++) {
							if((*it_new_b)->nodo->getNodeID() == (*it_figli)->nodo->getNodeID()) {
								already_present = true;
								break;
							}
						}

						if(!already_present) {		// non è già presente, lo aggiungo
							newBoundary.push_back(*it_figli);
						}
					}
				}

				//cout << "Grafo::findBestTree: " << "Prima di aggiungere: ";
				//local->coutString();

				// elimino il nodo dalla border e lo disattivo per evitare cicli e lo aggiungo all'albero
				(*it_border)->activeMVC[thr_idx] = false;
				local->addNode(prevNode, *it_border);

				//cout << "Grafo::findBestTree: " << "Dopo di aggiungere: ";
				//local->coutString();

				// CHIAMATA RICORSIVA!
				findBestTree(newBoundary, budget - cost_step, radius, *it_border, local, global,
						actualTreeCost + cost_step, actualTreeDistanceCost + dist_cost_step,
						actualTreeWidth + widthGain_step, actualTreeDistanceStemStepCost + distanceStemStepCost,
						thr_idx);

				// riattivo il nodo e lo tolgo dall'albero local
				(*it_border)->activeMVC[thr_idx] = true;
				local->removeNode(prevNode, *it_border);

				//cout << "Grafo::findBestTree: " << "Dopo di togliere: ";
				//local->coutString();

			}
		}
	}

	if(checkTree) {
		//cout << "Grafo::findBestTree: " << "Checking Tree" << endl;

		// Controllo il grafo a partire dal nodo prevNode e prendo tutti quell disattivi
		if( (global == NULL) || (global->nodo == NULL)

				||

				(actualTreeWidth > global->getStemWidth())

				||

				(	(actualTreeWidth == global->getStemWidth()) &&
					(actualTreeCost < global->getStemCost()))

				||

				(	(actualTreeWidth == global->getStemWidth()) &&
					(actualTreeCost == global->getStemCost()) &&
					(actualTreeDistanceCost < global->getDistanceCost()))

				||

				(	(actualTreeWidth == global->getStemWidth()) &&
					(actualTreeCost == global->getStemCost()) &&
					(actualTreeDistanceCost == global->getDistanceCost()) &&
					(actualTreeDistanceStemStepCost < global->getDistanceStemStepCost()))

			) {

			// BENE! ho trovato un albero migliore! Cancello quello vecchio e ne creo uni nuovo
			if (global != NULL) {
				if  (global->nodo != NULL) {
					// libera lo spazio del vecchio grafo
					global->clearAll();
				}
				free(global);
			}

			// creo il nuovo albero
			global = local->cloneGraph();

			//setto il costo e peso attuale
			global->setStemCost(actualTreeCost);
			global->setDistanceCost(actualTreeDistanceCost);
			global->setStemWidth(actualTreeWidth);
			global->setDistanceStemStepCost(actualTreeDistanceStemStepCost);
		}
	}
}

Grafo *Grafo::cloneGraph(void) {
	Grafo *cloned = new Grafo();

	if (nodo != NULL) {
		list<Grafo *>::iterator it;

		cloned->nodo = nodo;

		for (it = figli.begin(); it != figli.end(); it++) {
			Grafo *newFiglio = (*it)->cloneGraph();
			cloned->figli.push_back(newFiglio);
		}

		// unisco tutte le liste circolari dei figli con la mia
		for (it = cloned->figli.begin(); it != cloned->figli.end(); it++) {
			Grafo *prev_next, *next_prev;

			prev_next = cloned->nextGraph;
			next_prev = cloned->nextGraph->previousGraph;

			cloned->nextGraph->previousGraph = (*it)->previousGraph;
			cloned->nextGraph = *it;

			(*it)->previousGraph->nextGraph = prev_next;
			(*it)->previousGraph = next_prev;
		}
	}

	return cloned;
}

void Grafo::clearAll(void) {
	Grafo *g = this;

	do {
		Grafo *tmp = g->nextGraph;

		if(g != this) {
			free(g);
		}

		g = tmp;
	} while (g != this);


	// resetto tutto
	nodo = NULL;
	figli.clear();

	nextGraph = this;
	previousGraph = this;

	nStemNodes = 0;
	for (int i = 0; i < MAX_PARALLEL_THREADS; i++) {
		activeMVC[i] = false;
	}
	stemCost = -1;
}

void Grafo::coutString(void) {
	Grafo *g = this;

	do {
		if (g->nodo == NULL) continue;

		cout << g->nodo->getNodeID() << " ";
		g = g->nextGraph;
	} while(g != this);

	cout << endl;
}

Grafo *Grafo::insertStemNodeOnEdgeOk(double nOfRadios, double radius) {
	list<Grafo *>::iterator it, it2;
	Grafo *gp;
	Grafo *ris = new Grafo(nodo);

	//setto il peso dell'albero calcolato
	ris->setStemWidth(stemWidth);

	// inizializzo il costo ad 1
	ris->setStemCost(1);

	for (it = figli.begin(); it != figli.end(); it++) {
		gp = *it;

		if (gp->nodo->isSteinerNode()) {
			Grafo *nodes_child[3];
			int node_cost[3];
			int i = 0;
			int min_cost = 10000000;

			// mi salvo i tre punti del grafo incidenti sullo steiner
			nodes_child[i++] = ris;
			// il nodo steiner ha sempre due figli
			for(it2 = gp->figli.begin(); it2 != gp->figli.end(); it2++) {
				if(i < 3) {
					nodes_child[i++] = *it2;
				}
			}

			// prima calcolo per i tre archi il costo minore
			// calcolo da dove partire ( provo da tutti e tre i vertici e vedo il migliore )
			for (int j = 0; j < 3; j++) {
				// provo a calcolare il costo a partire da ogniuno dei tre vertici e alla fine prendo il meno costoso
				// (costeranno tutti uguale??? mah!)
				int _u1, _u2, _u3, _idx2, _idx3;
				double _r1, _r2, _g12, _g13, _g23;
				int tot_cost;

				// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
				_u1 = floor(nodes_child[j]->nodo->pos.distance(gp->nodo->pos) / radius);	 // non metto il nodo sullo steiner
				if (nodes_child[j]->nodo->pos.distance(gp->nodo->pos) == radius) {
					_u1 = 0;
				}

				// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
				_r1 = nodes_child[j]->nodo->pos.distance(gp->nodo->pos) - (((double) _u1) * radius);

				// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
				// sui segmenti rimanenti steiner<->2, steiner<->3
				_g12 = _g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r1 / radius) * (M_SQRT3 / 2.0)) );

				// cerco il segmento tra 2 e 3 più lungo dallo stainer
				if (	(nodes_child[((j + 1) % 3)]->nodo->pos.distance(gp->nodo->pos)) >
				(nodes_child[((j + 2) % 3)]->nodo->pos.distance(gp->nodo->pos)) ) {
					_idx2 = ((j + 1) % 3);
					_idx3 = ((j + 2) % 3);
				}
				else {
					_idx2 = ((j + 2) % 3);
					_idx3 = ((j + 1) % 3);
				}

				if (_g12 >= nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos)) {
					// controllo se il nodo si trova nel raggio di copertura del precedente
					_u2 = 0;	// mi serve solo 1 per coprire il nodo

					_r2 = nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos);
				}
				else {
					_u2 = ceil((nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos) - _g12) / radius);

					_r2 = _g12;
				}

				_g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r2 / radius) * (M_SQRT3 / 2.0)) );

				if (max(_g13, _g23) >= nodes_child[_idx3]->nodo->pos.distance(gp->nodo->pos)) {
					_u3 = 0;
				}
				else {
					_u3 = ceil((nodes_child[_idx3]->nodo->pos.distance(gp->nodo->pos) - max(_g13, _g23)) / radius);
				}

				tot_cost = _u1 + _u2 + _u3;
				if (tot_cost < min_cost) {
					node_cost[j] = _u1;
					node_cost[_idx2] = _u2;
					node_cost[_idx3] = _u3;
				}
			}

			// ora che ho calcolato il costo in stem-node di ogni arco, li aggiungo
			Grafo *parent[3];
			parent[0] = parent[1] = parent[2] = ris;
			for (int j = 0; j < 3; j++) {
				if (node_cost[j] > 0) {
					Coordinates pointerUnitVector;
					double start_offset;

					if (j == 0) {
						pointerUnitVector = (gp->nodo->pos - nodes_child[j]->nodo->pos) /
								nodes_child[j]->nodo->pos.distance(gp->nodo->pos);
						start_offset = 0;
					}
					else {
						pointerUnitVector = (nodes_child[j]->nodo->pos - gp->nodo->pos) /
								nodes_child[j]->nodo->pos.distance(gp->nodo->pos);

						start_offset = nodes_child[j]->nodo->pos.distance(gp->nodo->pos) - ((node_cost[j] + 1) * radius);
					}

					for (int k = 0; k < node_cost[j]; k++) {
						StemIsland *newNode = new StemIsland(nOfRadios, radius);
						Grafo *newGrafo = new Grafo(newNode);
						Coordinates startingPoint;

						if (j == 0) {
							startingPoint = nodes_child[j]->nodo->pos;
						}
						else {
							startingPoint = gp->nodo->pos;
						}

						newNode->pos = startingPoint +
								(pointerUnitVector * start_offset) +
								(pointerUnitVector * ((((double) k) + 1.0) * radius));

						// lo aggiungo alla lista dei miei figli
						parent[j]->figli.push_back(newGrafo);

						// lo inserisco nella lista circolare
						newGrafo->nextGraph = ris->nextGraph;
						newGrafo->previousGraph = ris;
						ris->nextGraph->previousGraph = newGrafo;
						ris->nextGraph = newGrafo;

						ris->setStemCost(ris->getStemCost() + 1);

						parent[j] = newGrafo;

						if (j == 0) {
							parent[1] = parent[2] = parent[0];
						}
					}
				}
			}

			for (int j = 1; j < 3; j++) {
				Grafo *tmp1, *tmp2;

				// chiamo la ricorsione per i due figli dello stainer divers da quello di partenza (j == 0)
				Grafo *childGraph = nodes_child[j]->insertStemNodeOnEdgeOk(nOfRadios, radius);

				// attacco il grafo della ricorsione sull'ultimo nodo creato
				parent[j]->figli.push_back(childGraph);

				// lo inserisco nella lista circolare
				tmp1 = ris->nextGraph;
				tmp2 = ris->nextGraph->previousGraph;
				ris->nextGraph = childGraph;
				ris->nextGraph->previousGraph = childGraph->previousGraph;
				childGraph->previousGraph->nextGraph = tmp1;
				childGraph->previousGraph = tmp2;

				// aggiorno i valori del costo e peso
				ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
				ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
			}

		}
		else {
			double dist = nodo->pos.distance(gp->nodo->pos);
			Coordinates pointerUnitVector = (gp->nodo->pos - nodo->pos) / dist;
			Grafo *parent = ris;

			// calcolo le posizioni dei nodi sull'arco
			if(dist > radius) {
				int nStemToAdd = floor(dist / radius);

				for (int i = 0; i < nStemToAdd; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodo->pos + (pointerUnitVector * ((((double) i) + 1.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent = newGrafo;
				}
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph = gp->insertStemNodeOnEdgeOk(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent->figli.push_back(childGraph);

			// lo inserisco nella lista circolare
			Grafo *tmp1, *tmp2;
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph;
			ris->nextGraph->previousGraph = childGraph->previousGraph;
			childGraph->previousGraph->nextGraph = tmp1;
			childGraph->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
		}
	}

	return ris;
}

Grafo *Grafo::insertStemNodeOnEdgeFinal(double nOfRadios, double radius) {
	list<Grafo *>::iterator it, it2;
	Grafo *gp;
	Grafo *ris = new Grafo(nodo);

	//setto il peso dell'albero calcolato
	ris->setStemWidth(stemWidth);

	// inizializzo il costo ad 1
	ris->setStemCost(1);

	//cout << "START: Grafo::insertStemNodeOnEdgeFinal" << endl;

	for (it = figli.begin(); it != figli.end(); it++) {
		gp = *it;

		//cout << "Node " << gp->nodo->getNodeID() << " is Steiner? " << gp->nodo->isSteinerNode() << endl;

		if (gp->nodo->isSteinerNode()) {
			Grafo *nodes_child[3];
			Grafo *parent[3];
			Grafo *parentTmp;
			Grafo *tmp1, *tmp2, *childGraph;
			int i = 0;
			int _u1, _u2, _u3, _idx2, _idx3;
			double _r1, _r2, _g12, _g13, _g23;
			Coordinates pointerUnitVector;

			parent[0] = parent[1] = parent[2] = parentTmp = ris;

			// mi salvo i tre punti del grafo incidenti sullo steiner
			nodes_child[i++] = ris;
			//cout << "Il nodo di indice 0 è: " << nodes_child[0]->nodo->getNodeID() << endl;
			// il nodo steiner ha sempre due figli
			for(it2 = gp->figli.begin(); it2 != gp->figli.end(); it2++) {
				if(i < 3) {
					nodes_child[i++] = *it2;
					//cout << "Il nodo di indice " << i << " è: " << nodes_child[(i-1)]->nodo->getNodeID() << endl;
				}
			}

			// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
			_u1 = ceil(nodes_child[0]->nodo->pos.distance(gp->nodo->pos) / radius) - 1;	 // non metto il nodo sullo steiner
			if (_u1 < 0) {
				_u1 = 0;
			}
			/*if (nodes_child[0]->nodo->pos.distance(gp->nodo->pos) == radius) {
				_u1 = 0;
			}*/

			//cout << "u1 = " << _u1 << endl;

			if (_u1 > 0) {
				pointerUnitVector = (gp->nodo->pos - nodes_child[0]->nodo->pos) /
						nodes_child[0]->nodo->pos.distance(gp->nodo->pos);

				for (int k = 0; k < _u1; k++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodes_child[0]->nodo->pos +
							(pointerUnitVector * ((((double) k) + 1.0) * radius));

					//cout << "Inserisco il nodo " << newNode->getNodeID() << " in posizione: " << newNode->pos << endl;

					// lo aggiungo alla lista dei miei figli
					parent[0]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[1] = parent[2] = parent[0] = parentTmp = newGrafo;
				}
			}

			// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
			_r1 = nodes_child[0]->nodo->pos.distance(gp->nodo->pos) - (((double) _u1) * radius);

			// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
			// sui segmenti rimanenti steiner<->2, steiner<->3
			_g12 = _g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r1 / radius) * (M_SQRT3 / 2.0)) );

			// cerco il segmento tra 2 e 3 più lungo dallo stainer
			if (	(nodes_child[1]->nodo->pos.distance(gp->nodo->pos)) >
			(nodes_child[2]->nodo->pos.distance(gp->nodo->pos)) ) {
				_idx2 = 1;
				_idx3 = 2;
			}
			else {
				_idx2 = 2;
				_idx3 = 1;
			}

			if (_g12 >= nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos)) {
				// controllo se il nodo si trova nel raggio di copertura del precedente
				_u2 = 0;	// mi serve solo 1 per coprire il nodo

				_r2 = nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos);
			}
			else {
				_u2 = ceil((nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos) - _g12) / radius);

				_r2 = _g12;

				// aggiungo gli stem
				pointerUnitVector = (nodes_child[_idx2]->nodo->pos - gp->nodo->pos) /
						nodes_child[_idx2]->nodo->pos.distance(gp->nodo->pos);

				for (int k = 0; k < _u2; k++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = gp->nodo->pos +
							(pointerUnitVector * _g12) +
							(pointerUnitVector * ((((double) k) + 0.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent[1]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[1] = newGrafo;

					if(k == 0) {
						parentTmp = newGrafo;
					}
				}
			}

			// chiamo la ricorsione per i due figli dello stainer divers da quello di partenza (j == 0)
			childGraph = nodes_child[_idx2]->insertStemNodeOnEdgeFinal(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[1]->figli.push_back(childGraph);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;
			ris->nextGraph = childGraph;
			ris->nextGraph->previousGraph = childGraph->previousGraph;
			childGraph->previousGraph->nextGraph = tmp1;
			childGraph->previousGraph = tmp2;

			// aggiorno i valori del costo e peso
			ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());


			_g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r2 / radius) * (M_SQRT3 / 2.0)) );

			if (_g23 > _g13) {
				parent[2] = parentTmp;
			}

			//parent[2] = parent[0];

			if (max(_g13, _g23) >= nodes_child[_idx3]->nodo->pos.distance(gp->nodo->pos)) {
				_u3 = 0;
			}
			else {
				_u3 = ceil((nodes_child[_idx3]->nodo->pos.distance(gp->nodo->pos) - max(_g13, _g23)) / radius);

				// aggiungo gli stem
				pointerUnitVector = (nodes_child[_idx3]->nodo->pos - gp->nodo->pos) /
						nodes_child[_idx3]->nodo->pos.distance(gp->nodo->pos);

				for (int k = 0; k < _u3; k++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = gp->nodo->pos +
							(pointerUnitVector * max(_g13, _g23)) +
							(pointerUnitVector * ((((double) k) + 0.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent[2]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[2] = newGrafo;
				}
			}

			// chiamo la ricorsione per i due figli dello stainer divers da quello di partenza (j == 0)
			childGraph = nodes_child[_idx3]->insertStemNodeOnEdgeFinal(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[2]->figli.push_back(childGraph);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;
			ris->nextGraph = childGraph;
			ris->nextGraph->previousGraph = childGraph->previousGraph;
			childGraph->previousGraph->nextGraph = tmp1;
			childGraph->previousGraph = tmp2;

			// aggiorno i valori del costo e peso
			ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
/*
			if(_idx2 != 1) {
				// c'è una discordanza tra i due, li swappo
				Grafo *tmpSwap = nodes_child[1];
				nodes_child[1] = nodes_child[2];
				nodes_child[2] = tmpSwap;

			}

			for (int j = 1; j < 3; j++) {
				Grafo *tmp1, *tmp2;

				// chiamo la ricorsione per i due figli dello stainer divers da quello di partenza (j == 0)
				Grafo *childGraph = nodes_child[j]->insertStemNodeOnEdgeFinal(nOfRadios, radius);

				// attacco il grafo della ricorsione sull'ultimo nodo creato
				parent[j]->figli.push_back(childGraph);

				// lo inserisco nella lista circolare
				tmp1 = ris->nextGraph;
				tmp2 = ris->nextGraph->previousGraph;
				ris->nextGraph = childGraph;
				ris->nextGraph->previousGraph = childGraph->previousGraph;
				childGraph->previousGraph->nextGraph = tmp1;
				childGraph->previousGraph = tmp2;

				// aggiorno i valori del costo e peso
				ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
				ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
			}
*/
		}
		else {
			double dist = nodo->pos.distance(gp->nodo->pos);
			Coordinates pointerUnitVector = (gp->nodo->pos - nodo->pos) / dist;
			Grafo *parent = ris;

			// calcolo le posizioni dei nodi sull'arco
			if(dist > radius) {
				int nStemToAdd = floor(dist / radius);
				if (dist == radius) {
					nStemToAdd = 0;
				}

				for (int i = 0; i < nStemToAdd; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodo->pos + (pointerUnitVector * ((((double) i) + 1.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent = newGrafo;
				}
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph = gp->insertStemNodeOnEdgeFinal(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent->figli.push_back(childGraph);

			// lo inserisco nella lista circolare
			Grafo *tmp1, *tmp2;
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph;
			ris->nextGraph->previousGraph = childGraph->previousGraph;
			childGraph->previousGraph->nextGraph = tmp1;
			childGraph->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
		}
	}

	return ris;
}

Grafo *Grafo::insertStemNodeOnEdge(double nOfRadios, double radius) {
	list<Grafo *>::iterator it, it2;
	Grafo *gp;
	Grafo *ris = new Grafo(nodo);

	//setto il peso dell'albero calcolato
	ris->setStemWidth(stemWidth);

	// inizializzo il costo ad 1
	ris->setStemCost(1);

	for (it = figli.begin(); it != figli.end(); it++) {
		gp = *it;

		// calcolo le posizioni dei nodi sull'arco
		if (gp->nodo->isSteinerNode()) {
			// prima mi occupo di andare verso lo steiner node
			//double dist;
			Node *nodes[3];
			Grafo *nodes_child[3];
			Grafo *parent[3];
			Grafo *parentTmp;
			Grafo *tmp1, *tmp2;
			int u1, u2, u3, idx2, idx3, i, indexParent;
			//double r1, r2, g12, g13, g23;
			//int idx2, idx3, i, indexParent;
			double g12, g13, g23;

			int tot_cost[3];
			int minCost = 100000000;

			//int archCost[3][3];

			parent[0] = parent[1] = parent[2] = ris;
			i = 0;

			nodes[i] = ris->nodo;
			nodes_child[i] = ris;
			i++;
			// il nodo steiner ha sempre due figli
			for(it2 = gp->figli.begin(); it2 != gp->figli.end(); it2++) {
				if(i < 3) {
					nodes[i] = (*it2)->nodo;
					nodes_child[i] = *it2;

					i++;
				}
			}

			indexParent = 0;	// con indexParent indico l'indice del nodo di partenza
			idx2 = 1;
			idx3 = 2;

			// calcolo da dove partire
			for (int j = 0; j < 3; j++) {
				// provo a calcolare il costo a partire da ogniuno dei tre vertici e alla fine prendo il meno costoso
				// (costeranno tutti uguale??? mah!)
				int _u1, _u2, _u3, _idx2, _idx3;
				double _r1, _r2, _g12, _g13, _g23;

				// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
				_u1 = floor(nodes[((j + 0) % 3)]->pos.distance(gp->nodo->pos) / radius);	 // non metto il nodo sullo steiner
				if (nodes[((j + 0) % 3)]->pos.distance(gp->nodo->pos) == radius) {
					_u1 = 0;
				}

				// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
				_r1 = nodes[((j + 0) % 3)]->pos.distance(gp->nodo->pos) - (((double) _u1) * radius);

				// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
				// sui segmenti rimanenti steiner<->2, steiner<->3
				_g12 = _g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r1 / radius) * (M_SQRT3 / 2.0)) );

				// cerco il segmento tra 2 e 3 più lungo dallo stainer
				if (	(nodes[((j + 1) % 3)]->pos.distance(gp->nodo->pos)) >
				(nodes[((j + 2) % 3)]->pos.distance(gp->nodo->pos)) ) {
					_idx2 = 1;
					_idx3 = 2;
				}
				else {
					_idx2 = 2;
					_idx3 = 1;
				}

				if (_g12 >= nodes[((j + _idx2) % 3)]->pos.distance(gp->nodo->pos)) {
					// controllo se il nodo si trova nel raggio di copertura del precedente
					_u2 = 0;	// mi serve solo 1 per coprire il nodo

					_r2 = nodes[((j + _idx2) % 3)]->pos.distance(gp->nodo->pos);
				}
				else {
					_u2 = ceil((nodes[((j + _idx2) % 3)]->pos.distance(gp->nodo->pos) - _g12) / radius);

					_r2 = _g12;
				}

				_g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((_r2 / radius) * (M_SQRT3 / 2.0)) );


				if (max(_g13, _g23) >= nodes[((j + _idx2) % 3)]->pos.distance(gp->nodo->pos)) {
					_u3 = 0;
				}
				else {
					_u3 = ceil((nodes[((j + _idx3) % 3)]->pos.distance(gp->nodo->pos) - max(_g13, _g23)) / radius);
				}

				tot_cost[j] = _u1 + _u2 + _u3;
				//archCost[j][0] = _u1;
				//archCost[j][_idx2] = _u2;
				//archCost[j][_idx3] = _u3;

				if (tot_cost[j] < minCost) {
					indexParent = j;
					idx2 = _idx2;
					idx3 = _idx3;
					g12 = g13 = _g12;
					g23 = _g23;
					u1 = _u1;
					u2 = _u2;
					u3 = _u3;
					minCost = tot_cost[j];
				}
			}

			//inserisco i nodi sugli archi
			if (u1 > 0) {
				Coordinates pointerUnitVector = (gp->nodo->pos - nodes[indexParent]->pos) /
						nodes[indexParent]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u1; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodes[indexParent]->pos + (pointerUnitVector * ((((double) i) + 1.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent[0]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[0] = newGrafo;
				}
			}

			parent[1] = parent[2] = parentTmp = parent[0];

			if (u2 > 0) {
				Coordinates pointerUnitVector = (nodes[((indexParent + idx2) % 3)]->pos - gp->nodo->pos) /
						nodes[((indexParent + idx2) % 3)]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u2; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					//newNode->pos = gp->nodo->pos + (pointerUnitVector * ((((double) i) * radius) + g12));
					newNode->pos = gp->nodo->pos + (pointerUnitVector * (((double) i) * radius))
													+ (pointerUnitVector * g12);

					// lo aggiungo alla lista dei miei figli
					parent[1]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[1] = newGrafo;

					if(parentTmp == parent[0]) {
						parentTmp = newGrafo;
					}
				}
			}

			if (g23 > g13) {
				parent[2] = parentTmp;
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph2 = nodes_child[((indexParent + idx2) % 3)]->insertStemNodeOnEdge(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[1]->figli.push_back(childGraph2);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph2;
			ris->nextGraph->previousGraph = childGraph2->previousGraph;
			childGraph2->previousGraph->nextGraph = tmp1;
			childGraph2->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph2->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph2->getStemWidth());

			if (u3 > 0) {
				Coordinates pointerUnitVector = (nodes[((indexParent + idx3) % 3)]->pos - gp->nodo->pos) /
						nodes[((indexParent + idx3) % 3)]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u3; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = gp->nodo->pos + (pointerUnitVector * ((((double) i) * radius) + max(g13, g23)));

					// lo aggiungo alla lista dei miei figli
					parent[2]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[2] = newGrafo;
				}
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph3 = nodes_child[((indexParent + idx3) % 3)]->insertStemNodeOnEdge(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[2]->figli.push_back(childGraph3);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph3;
			ris->nextGraph->previousGraph = childGraph3->previousGraph;
			childGraph3->previousGraph->nextGraph = tmp1;
			childGraph3->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph3->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph3->getStemWidth());





/*
			// considero u1(nodes[0], steiner), u2(nodes[1], steiner), u3(nodes[2], steiner)
			dist = nodes[((indexParent + 0) % 3)]->pos.distance(gp->nodo->pos);
			u1 = floor(dist / radius);	 // non metto il nodo sullo steiner
			if (dist == radius) {
				u1 = 0;
			}

			if(dist > radius) {

				Coordinates pointerUnitVector = (gp->nodo->pos - nodes[((indexParent + 0) % 3)]->pos) /
						nodes[((indexParent + 0) % 3)]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u1; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodes[((indexParent + 0) % 3)]->pos + (pointerUnitVector * ((((double) i) + 1.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent[0]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[0] = newGrafo;
				}
			}

			parent[1] = parent[2] = parentTmp = parent[0];

			// r1 è la distanza dell'ultimo nodo calcolato fino allo steiner
			r1 = dist - (((double) u1) * radius);

			// g12 e g13 sono i guadagni che ho con l'ultimo nodo posizionato sul segmento 1 (steiner<->1)
			// sui segmenti rimanenti steiner<->2, steiner<->3
			g12 = g13 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r1 / radius) * (M_SQRT3 / 2.0)) );

			// cerco il segmento tra 2 e 3 più lungo dallo stainer
			if (	(nodes[indexParent + 1]->pos.distance(gp->nodo->pos)) >
			(nodes[indexParent + 2]->pos.distance(gp->nodo->pos)) ) {
				idx2 = 1;
				idx3 = 2;
			}
			else {
				idx2 = 2;
				idx3 = 1;
			}

			if (g12 >= nodes[((indexParent + idx2) % 3)]->pos.distance(gp->nodo->pos)) {
				// controllo se il nodo si trova nel raggio di copertura del precedente
				// non mi servono nodi, è già coperto
				r2 = nodes[((indexParent + idx2) % 3)]->pos.distance(gp->nodo->pos);
			}
			else {
				u2 = ceil((nodes[((indexParent + idx2) % 3)]->pos.distance(gp->nodo->pos) - g12) / radius);

				Coordinates pointerUnitVector = (nodes[((indexParent + idx2) % 3)]->pos - gp->nodo->pos) /
						nodes[((indexParent + idx2) % 3)]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u2; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					//newNode->pos = gp->nodo->pos + (pointerUnitVector * ((((double) i) * radius) + g12));
					newNode->pos = gp->nodo->pos + (pointerUnitVector * (((double) i) * radius))
							+ (pointerUnitVector * g12);

					// lo aggiungo alla lista dei miei figli
					parent[1]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[1] = newGrafo;

					if(parentTmp == parent[0]) {
						parentTmp = newGrafo;
					}
				}

				r2 = g12;
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph2 = nodes_child[((indexParent + idx2) % 3)]->insertStemNodeOnEdge(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[1]->figli.push_back(childGraph2);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph2;
			ris->nextGraph->previousGraph = childGraph2->previousGraph;
			childGraph2->previousGraph->nextGraph = tmp1;
			childGraph2->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph2->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph2->getStemWidth());

			g23 = ((2.0 * radius) / M_SQRT3) * sin( (M_PI / 3.0) - asin((r2 / radius) * (M_SQRT3 / 2.0)) );

			if (g23 > g13) {
				parent[2] = parentTmp;
			}

			if (max(g13, g23) >= nodes[((indexParent + idx3) % 3)]->pos.distance(gp->nodo->pos)) {
				// controllo se il nodo si trova nel raggio di copertura del precedente
				// non mi servono nodi, è già coperto
				u3 = 1;

				parent[2] = parent[0];
			}
			else {
				u3 = ceil((nodes[((indexParent + idx3) % 3)]->pos.distance(gp->nodo->pos) - max(g13, g23)) / radius);

				Coordinates pointerUnitVector = (nodes[((indexParent + idx3) % 3)]->pos - gp->nodo->pos) /
						nodes[((indexParent + idx3) % 3)]->pos.distance(gp->nodo->pos);

				for (i = 0; i < u3; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = gp->nodo->pos + (pointerUnitVector * ((((double) i) * radius) + max(g13, g23)));

					// lo aggiungo alla lista dei miei figli
					parent[2]->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent[2] = newGrafo;
				}
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph3 = nodes_child[((indexParent + idx3) % 3)]->insertStemNodeOnEdge(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent[2]->figli.push_back(childGraph3);

			// lo inserisco nella lista circolare
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph3;
			ris->nextGraph->previousGraph = childGraph3->previousGraph;
			childGraph3->previousGraph->nextGraph = tmp1;
			childGraph3->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph3->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph3->getStemWidth());
*/

		}
		else {
			double dist = nodo->pos.distance(gp->nodo->pos);
			Coordinates pointerUnitVector = (gp->nodo->pos - nodo->pos) / dist;
			Grafo *parent = ris;

			if(dist > radius) {
				int nStemToAdd = floor(dist / radius);

				for (int i = 0; i < nStemToAdd; i++) {
					StemIsland *newNode = new StemIsland(nOfRadios, radius);
					Grafo *newGrafo = new Grafo(newNode);

					newNode->pos = nodo->pos + (pointerUnitVector * ((((double) i) + 1.0) * radius));

					// lo aggiungo alla lista dei miei figli
					parent->figli.push_back(newGrafo);

					// lo inserisco nella lista circolare
					newGrafo->nextGraph = ris->nextGraph;
					newGrafo->previousGraph = ris;
					ris->nextGraph->previousGraph = newGrafo;
					ris->nextGraph = newGrafo;

					ris->setStemCost(ris->getStemCost() + 1);

					parent = newGrafo;
				}
			}

			// chiamo la funzione ricorsivamente (speriamo che non ci siano cicli.... non sono gestiti)
			Grafo *childGraph = gp->insertStemNodeOnEdge(nOfRadios, radius);

			// attacco il grafo della ricorsione sull'ultimo nodo creato
			parent->figli.push_back(childGraph);

			// lo inserisco nella lista circolare
			Grafo *tmp1, *tmp2;
			tmp1 = ris->nextGraph;
			tmp2 = ris->nextGraph->previousGraph;

			ris->nextGraph = childGraph;
			ris->nextGraph->previousGraph = childGraph->previousGraph;
			childGraph->previousGraph->nextGraph = tmp1;
			childGraph->previousGraph = tmp2;

			ris->setStemCost(ris->getStemCost() + childGraph->getStemCost());
			ris->setStemWidth(ris->getStemWidth() + childGraph->getStemWidth());
		}
	}

	return ris;
}


